package main

import "fmt"

func main() {
	input := &ListNode{
		Val: 5,
		Next: &ListNode{
			Val: 8,
			Next: &ListNode{
				Val: 10,
				Next: &ListNode{
					Val: 1,
					Next: &ListNode{
						Val: 3,
						Next: &ListNode{
							Val: 2,
							Next: &ListNode{
								Val: 4,
								Next: &ListNode{
									Val: 11,
								},
							},
						},
					},
				},
			},
		},
	}
	res := sortList(input)
	for tmp := res; tmp != nil; tmp = tmp.Next {
		fmt.Print(tmp.Val, "   ")
	}

	nums := []int{4, 5, 8, 7, 6, 3, 1, 10}
	mergeSort(nums)
	fmt.Println(nums)
}

type ListNode struct {
	Val  int
	Next *ListNode
}

//链表归并排序
func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	fast, slow := head, head
	for fast.Next != nil {
		fast = fast.Next
		if fast.Next != nil {
			fast = fast.Next
		} else {
			break
		}
		slow = slow.Next
	}
	right := slow.Next
	slow.Next = nil
	resRight := sortList(right)
	resLeft := sortList(head)
	return merge(resLeft, resRight)
}

func merge(list1, list2 *ListNode) *ListNode {
	res := &ListNode{}
	tail := res
	for ; list1 != nil && list2 != nil; tail = tail.Next {
		if list1.Val < list2.Val {
			tail.Next = list1
			list1 = list1.Next
		} else {
			tail.Next = list2
			list2 = list2.Next
		}
	}
	if list1 == nil {
		tail.Next = list2
	} else {
		tail.Next = list1
	}
	return res.Next
}

//普通归并排序
func mergeSort(input []int) {
	if len(input) <= 1 {
		return
	}
	mid := len(input) / 2
	mergeSort(input[:mid])
	mergeSort(input[mid:])
	mergeSlice(input, mid)
}

func mergeSlice(input []int, mid int) {
	tmp := make([]int, len(input))
	count := 0
	i, j := 0, mid
	for ; i < mid && j < len(input); count++ {
		if input[i] <= input[j] {
			tmp[count] = input[i]
			i++
		} else {
			tmp[count] = input[j]
			j++
		}
	}
	for ; i < mid; count++ {
		tmp[count] = input[i]
		i++
	}
	for ; j < len(input); count++ {
		tmp[count] = input[j]
		j++
	}
	copy(input, tmp)
}
